import java.io.*;
import java.util.*;

class Read {
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
}

public class Main {
    public static Read in = new Read();
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        int d = in.nextInt(), n = in.nextInt();
//        int[] weight = new int[n];
        int[] volume = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
//            weight[i] = in.nextInt();
            volume[i] = in.nextInt();
            value[i] = in.nextInt();
        }
        System.out.println(knapsack2(volume, value, d, n));
    }

    private static int knapsack2(int[] volume, int[] value, int d, int n) {
        int[] dp = new int[d + 1];
        for (int i = 0; i < n; i++) {
            for (int j = d; j >= volume[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - volume[i]] + value[i]);
            }
        }
        return dp[d];
    }

    public long maxWater(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        long water = 0;
        int leftmax = 0;
        int rightmax = 0;
        while (left < right) {
            //确定左边的最高柱子
            leftmax = Math.max(leftmax, arr[left]);
            //确定左边的最高柱子
            rightmax = Math.max(rightmax, arr[right]);
            //那么桶的高度就是leftmax和rightmax中最小的那个
            if (leftmax < rightmax) {
                //桶的高度是leftmax
                water += (leftmax - arr[left++]);
            } else {
                //桶的高度是rightmax
                water += (rightmax - arr[right--]);
            }
        }
        return water;
    }

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode newHead = new ListNode(0, head);
        ListNode cur = newHead;
        while(cur.next != null&&cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while(cur.next != null&&cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            }
            else {
                cur = cur.next;
            }
        }
        return newHead.next;
    }

    //01背包
    public static int knapsack(int[] weight,int[] volume ,int[] value ,int c, int d, int n) {
        int[][] dp = new int[d + 1][c + 1];
        for (int i = 0; i < n; i++) {
            for (int j = c; j >= 0; j--) {
                for (int k = d; k >= 0; k--) {
                    if (j >= weight[i] && k >= volume[i]) {
                        dp[k][j] = Math
                                .max(dp[k][j], dp[k - volume[i]][j - weight[i]] + value[i]);
                    }
                }
            }
        }
        return dp[d][c];
    }

    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return count;
    }


    private void dfs(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        }else {
            dfs(nums, target, index + 1, sum + nums[index]);
            dfs(nums, target, index + 1, sum - nums[index]);
        }
    }

    public int findTargetSumWays2(int[] nums, int target) {
        int sum = 0;
        for (int i = 0 ;i < nums.length;i++) {
            sum += nums[i];
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = (sum + target)/2 + 1;
        if (n < 0) {
            return 0;
        }
        int[][] dp = new int[nums.length + 1][n];
        dp[0][0] = 1;
        for (int i = 1;i <= nums.length;i++) {
            for (int j = 0; j < n;j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }

        }
        return dp[nums.length][n-1];
    }

    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();
        q.add(new Pair<TreeNode, Integer>(root, 1));
        int ret = 0;
        while (!q.isEmpty()) {
            Pair<TreeNode, Integer> t1 = q.get(0);
            Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);
            ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for (Pair<TreeNode, Integer> t : q) {
                TreeNode node = t.getKey();
                int index = t.getValue();
                if (node.left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.left, index*2));
                }
                if (node.right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.right, index*2+1));
                }
            }
            q = tmp;
        }
        return ret;
    }

    private List<List<Integer>> result;
    private List<Integer> path;
    public List<List<Integer>> findSubsequences(int[] nums) {
        result = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums, Integer.MIN_VALUE, 0);
        return result;
    }
    private void dfs(int[] nums,int last , int start) {
        if (start == nums.length) {
            if (path.size() >= 2){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        if (nums[start] >= last) {
            path.add(nums[start]);
            dfs(nums, nums[start], start + 1);
            path.remove(path.size() - 1);
        }
        if (nums[start] != last) {
            dfs(nums, last, start + 1);
        }
    }

    public List<List<Integer>> levelOrder(_Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<_Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                _Node node = queue.poll();
                list.add(node.val);
                for (_Node child : node.children) {
                    queue.offer(child);
                }

            }
            result.add(list);
        }
        return result;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode cur = head;
        Stack<Integer> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        while (head != null) {
            if (head.val != stack.pop()) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] hash = new int[26];
        for (int i = 0;i < s1.length();i++) {
            hash[s1.charAt(i) - 'a']++;
        }
        for (int i = 0;i < s2.length();i++) {
            if (hash[s2.charAt(i) - 'a'] == 0) {
                return false;
            }
            hash[s2.charAt(i) - 'a']--;
        }
        return true;
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<List<Integer>> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0;i < size;i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            result.add(0, list);
        }
        return result;
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean flag = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            Deque<Integer> list = new LinkedList<>();
            for (int i = 0;i < size;i++) {
                TreeNode node = queue.poll();
                if (flag) {
                    list.offerLast(node.val);
                }
                else {
                    list.offerFirst(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(new ArrayList<>(list));
            flag = !flag;
        }
        return result;
    }

    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0;i < s.length();i++) {
            if (!stack.isEmpty() && stack.peek() == s.charAt(i)) {
                stack.pop();
            }
            else {
                stack.push(s.charAt(i));
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }

    public String getHint(String secret, String guess) {
        int n = secret.length();
        int a = 0,b = 0;
        int[] hash1 = new int[10];
        int[] hash2 = new int[10];
        for (int i = 0;i < n;i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                a++;
            }
            else {
                hash1[secret.charAt(i) - '0']++;
                hash2[guess.charAt(i) - '0']++;
            }
        }
        for (int i = 0;i < 10;i++) {
            b += Math.min(hash1[i], hash2[i]);
        }
        return a + "A" + b + "B";
    }

    public boolean isAdditiveNumber(String num) {
        return dfs(num, num.length(), 0, 0, 0, 0);
    }

    private boolean dfs(String num, int length, int idx, long sum, long pre, int k) {
        if (idx == length) {
            return k > 2;
        }
        for (int i = idx;i < length;i++) {
            long cur = fetchCurValue(num, idx, i);
            if (cur == -1) {
                continue;
            }
            if (k >= 2 && cur > sum) {
                continue;
            }
            if (k < 2 || cur == sum) {
                if (dfs(num, length, i + 1, pre + cur, cur, k + 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    private long fetchCurValue(String num, int l, int r) {
        if (l < r && num.charAt(l) == '0') {
            return -1;
        }
        long res = 0;
        while (l <= r) {
            res = res * 10 + num.charAt(l++) - '0';
        }
        return res;
    }


    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode newHead = head;
        ListNode slow = getMidNode(head);
        ListNode cur = slow.next;
        slow.next = null;
        ListNode prev = getReserveNode(cur);
        merge(newHead, prev);
    }

    private static void merge(ListNode newHead, ListNode prev) {
        while (prev != null&& newHead != null) {
            ListNode headNext = newHead.next;
            ListNode prevNext = prev.next;

            newHead.next = prev;
            newHead = headNext;
            prev.next = newHead;
            prev = prevNext;
        }
    }

    private static ListNode getReserveNode(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    private static ListNode getMidNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!=null&&fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private int m, n, step;
    private int sum;
    private boolean[][] vis;
    private int ret;
    private int[] dx = {0, 0, -1, 1};
    private int[] dy = {1, -1, 0, 0};
    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        vis = new boolean[m][n];
        int bx = 0, by = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    bx = i;
                    by = j;
                }
                else if (grid[i][j] == 0) {
                    step++;
                }
            }
        }
        step += 2;
        vis[bx][by] = true;
        dfs(grid, bx, by, 1);
        return ret;
    }

    private void dfs(int[][] grid, int i, int j, int sum) {
        if (grid[i][j] == 2) {
            if (sum == this.step) {
                ret++;
            }
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == -1 || vis[x][y]) {
                continue;
            }
            vis[x][y] = true;
            dfs(grid, x, y, sum + 1);
            vis[x][y] = false;
        }
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode next = cur.left;
                TreeNode prev = next;
                while (prev.right != null) {
                    prev = prev.right;
                }
                prev.right = cur.right;
                cur.left = null;
                cur.right = next;
            }
            cur = cur.right;
        }

    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums3=new int[nums1.length+nums2.length];
        int k=0,i=0,j=0;
        while(i<nums1.length&&j<nums2.length){
            if(nums1[i]>nums2[j]){
                nums3[k++]=nums2[j++];
            }
            else{
                nums3[k++]=nums1[i++];
            }
        }
        if(i>=nums1.length){
            while(j<nums2.length){
                nums3[k++]=nums2[j++];
            }
        }
        if(j>=nums2.length){
            while(i<nums1.length){
                nums3[k++]=nums1[i++];
            }
        }
        if(nums3.length%2!=0){
            return (double)nums3[nums3.length/2];
        }
        double mid=(nums3[nums3.length/2]+nums3[nums3.length/2-1])/2.0;
        return mid;
    }

    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> set = new HashSet<>();
        String ans = "";
        for (String word : words) {
            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
                if (ans.length() < word.length()
                        || (ans.length() == word.length() && ans.compareTo(word) > 0)) {
                    ans = word;
                }
                set.add(word);
            }

        }
        return ans;
    }

    public int deleteGreatestValue(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            Arrays.sort(grid[i]);
        }
        int ans = 0;
        for (int j = 0; j < grid[0].length; j++) {
            int max = 0;
            for (int i = 0; i < grid.length; i++) {
                max = Math.max(max, grid[i][j]);
            }
            ans += max;
        }
        return ans;
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1;i < n;i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n-1][0];
    }

    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n][3];
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];
        for (int i = 1;i < n;i++) {
            dp[i][0] = Math.min(dp[i-1][1] + costs[i][0], dp[i-1][2] + costs[i][0]);
            dp[i][1] = Math.min(dp[i-1][0] + costs[i][1], dp[i-1][2] + costs[i][1]);
            dp[i][2] = Math.min(dp[i-1][0] + costs[i][2], dp[i-1][1] + costs[i][2]);
        }
        return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
    }

    public int mechanicalAccumulator(int target) {
        return target <= 0 ? 0 : target + mechanicalAccumulator(target - 1);
    }

    List<List<Integer>> res;
    List<Integer> path1;
    int l;
    public List<List<Integer>> subsets(int[] nums) {
        l = nums.length;
        res = new ArrayList<>();
        path1 = new ArrayList<>();
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int i) {
        res.add(new ArrayList<>(path1));
        for (int j = i; j < l; j++) {
            path1.add(nums[j]);
            dfs(nums, j + 1);
            path1.remove(path1.size() - 1);
        }
    }

    public int pathSum(TreeNode root, int target) {
        if (root == null) {
            return 0;
        }
        int ret = rootSum(root, target);
        ret += pathSum(root.left, target);
        ret += pathSum(root.right, target);
        return ret;
    }
    public int rootSum(TreeNode root, int target) {
        int ret = 0;
        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == target) {
            ret++;
        }
        ret += rootSum(root.left, target - val);
        ret += rootSum(root.right, target - val);
        return ret;
    }

}
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

class _Node {
    public int val;
    public List<_Node> children;

    public _Node() {}

    public _Node(int _val) {
        val = _val;
    }

    public _Node(int _val, List<_Node> _children) {
        val = _val;
        children = _children;
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class CQueue {

    private Queue<Integer> books;

    public CQueue() {
        books = new LinkedList<>();
    }

    public void appendTail(int value) {
        books.add(value);
    }

    public int deleteHead() {
        if (books.isEmpty()) {
            return -1;
        }
        return books.poll();
    }
}

class MyCircularQueue {
    private int[] elements;
    private int front;
    private int rear;
    private int size;

    public MyCircularQueue(int k) {
        elements = new int[k];
        front = 0;
        rear = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % elements.length;
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % elements.length;
        size--;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    public int Rear() {
        if (isEmpty()) {
        return -1;
        }
        return elements[(rear - 1 + elements.length) % elements.length];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == elements.length;
    }
}

class MedianFinder {
    private PriorityQueue<Integer> queMin;
    private PriorityQueue<Integer> queMax;

    public MedianFinder() {
        queMin = new PriorityQueue<>((a, b) -> (b - a));
        queMax = new PriorityQueue<>((a, b) -> (a - b));
    }

    public void addNum(int num) {
        if (queMin.isEmpty() || num <= queMin.peek()) {
            queMin.offer(num);
            if (queMin.size() > queMax.size() + 1) {
                queMax.offer(queMin.poll());
            }
        }
        else {
            queMax.offer(num);
            if (queMax.size() > queMin.size()) {
                queMin.offer(queMax.poll());
            }
        }

    }

    public double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.peek();
        }
        return (queMin.peek() + queMax.peek()) / 2.0;
    }
}